package code.starivan.leetcode;

import code.starivan.leetcode.common.ListNode;

/**
 * Created by Ivan on 2015/10/20.
 */

/*
Sort a linked list in O(n log n) time using constant space complexity.

        Show Tags
        Show Similar Problems


*/

public class N148_SortList {
    public static void test()
    {
        ListNode n1=new ListNode(1);
        ListNode n2=new ListNode(4);
        ListNode n3=new ListNode(3);
        ListNode n4=new ListNode(7);
        ListNode n5=new ListNode(2);
        ListNode n6=new ListNode(8);

        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        n4.next=n5;
        n5.next=n6;

        n1.printList();
        new N148_SortList().sortList(n1).printList();
    }

    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }

        ListNode mid=getMiddleNode(head);
        ListNode next=mid.next;
        mid.next=null;

        return merge(sortList(head),sortList(next));
    }

    private ListNode getMiddleNode(ListNode head){
        ListNode s=head;
        ListNode q=head;

        while (q!=null&&q.next!=null&&q.next.next!=null){
            s=s.next;
            q=q.next.next;
        }

        return s;
    }

    private ListNode merge(ListNode a,ListNode b){
        ListNode ret=new ListNode(-1);
        ListNode cur=ret;

        while (a!=null&&b!=null){
            if(a.val<b.val){
                cur.next=a;
                a=a.next;
            }else{
                cur.next=b;
                b=b.next;
            }

            cur=cur.next;
        }

        cur.next=a==null?b:a;
        return ret.next;
    }
}
